package 牛客网在线编程题库;

import java.util.HashSet;
import 牛客网在线编程题库.ListNode;

/**
 * 题目描述
 判断给定的链表中是否有环。如果有环则返回true，否则返回false。
 你能给出空间复杂度的解法么？
 */

public class _判断链表中是否有环 {
    /**
     * 散列表法
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 遍历指针
        ListNode cur = head;
        // 哈希表
        HashSet<ListNode> set = new HashSet<>();
        // 遍历
        while (cur != null) {
            if (set.contains(cur)) {
                return true;
            }else {
                // 将该结点加入到散列表中
                set.add(cur);
                cur = cur.next;
            }
        }
        return false;
    }

    /**
     * 双指针法(快慢指针)
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head) {
        // 校验合法性
        if (head == null) {
            return false;
        }
        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 当后面有元素时一直循环
        while (fast.next != null && fast.next.next != null && slow.next != null) {
            // 快指针一次走两步，慢指针一次走一步
            fast = fast.next.next;
            slow = slow.next;
            // 若两指针走了一圈后重合
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}
